package src.dp.sequence;

public class no5 {//最长回文子串
    /**
     * dp[i][j]含义：以 i开头 j结尾的串中 最长的回文子串 的内容为dp[i][j]
     * 递推公式：
     * s[i] == s[j]时：dp[i][j] = s[i] + dp[i+1][j-1] + s[j]
     * s[i] != s[j]时，把 i 或者 j 其中之一加进来，dp[i][j] = max(dp[i+1][j], dp[i][j-1])
     * 初始化：bdp[i][i] == s[i]
     * 遍历顺序：i 从上往下，j 从左往右
     */
    public static String longestPalindrome(String s) {
        int n = s.length();
        int len = 0;
        String  res =  "";
        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j-i <=1 || dp[i+1][j-1])) {
                    dp[i][j] = true;
                    len = Math.max(len, j-i);
                    if (j-i >= len) res = s.substring(i, j+1);
                }
            }
        }
        return res;

    }

    public static String longestPalindrome2(String s) {
        int n = s.length();
        int right=n/2;
        String res = String.valueOf(s.charAt(right));

        int left;
        if(n%2==0) left=right-1;
        else left=right;

        while(left>=0&&right<n){
            if(s.charAt(left)==s.charAt(right)){
                res=s.substring(left,right+1);
                left--;right++;
            }else if(s.charAt(left)==s.charAt(right-1)){
                res=s.substring(left,right);
                break;
            } else if (s.charAt(left+1)==s.charAt(right)) {
                res=s.substring(left+1,right+1);
                break;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "abb";
        String res = longestPalindrome(s);
        System.out.println(res);
    }

}
